package qjc.e_普通数组;

public class e5_缺失的第一个正数 {
    /**
     * 获取数组的长度，遍历数组，将每个正数放到它应该在的位置，
     * 当前位置的数字 nums[i] 应该放在 nums[nums[i] - 1] 的位置，
     * 例如，数字 1 应该放在索引 0 的位置，数字 2 应该放在索引 1 的位置，
     * 如果 nums[i] 是正数，并且在数组范围内，并且 nums[nums[i] - 1] 不等于 nums[i]，
     * 则交换 nums[i] 和 nums[nums[i] - 1]，再次遍历数组，
     * 找到第一个 nums[i] != i + 1 的位置，
     * 如果 nums[i] 不等于 i + 1，说明 i + 1 是缺失的第一个正数，
     * 如果所有位置都正确，返回 len + 1
     */
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            while (nums[i] > 0 && nums[i] <= len &&
            nums[nums[i] - 1] != nums[i]){
                swap(nums,nums[i] - 1,i);
            }
        }
        for (int i = 0; i < len; i++) {
            if(nums[i] != i + 1){
                return i + 1;
            }
        }
        return len + 1;
    }
    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
